\documentclass[10pt, a4paper, titlepage, oneside]{article}
\usepackage[top=2.5cm, bottom=2cm, left=2.5cm, right=1cm]{geometry}
%\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{gensymb}
\usepackage{multirow}
\usepackage{rotating}
\usepackage{listings}

% dot
%\usepackage{dot2texi}
%\usepackage{tikz}
%\usetikzlibrary{shapes,arrows}

% Font, accents
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{times}                % Otros: palatino, bookman, times

% Interactive index
\usepackage{hyperref}

% Spanish titles
\usepackage[spanish]{babel}

\lstset{language=Matlab}

% Make lists without bullets
%\renewenvironment{itemize}{
% \begin{list}{}{
%  \setlength{\leftmargin}{1.5em}
% }
%}{
% \end{list}
%}

% Document properties
\title{75.12 - Análisis Numérico - Grupo 2 - TP1}
\author{
	Federico Churca-Torrusio\\91352\\federico.churca@gmail.com \and
	Emanuel Cruz\\91513\\malon.emanuel@gmail.com\and
	Miguel Serigos\\91469\\miguelserigos@gmail.com}
\date{2013 - Verano\\
	Fecha de reentrega: 06 de marzo de 2013}
\hypersetup{
  colorlinks = true,
  urlcolor = red,
  pdflang = es,
  pdfauthor = {Federico Churca-Torrusio, Emanuel Cruz, Miguel Serigos},
  pdfproducer = {Federico Churca-Torrusio, Emanuel Cruz, Miguel Serigos},
  pdfcreator = pdflatex,
  pdftitle = {75.12 - Análisis Numérico - Grupo 2 - TP1},
  pdfsubject = {},
  pdfpagemode = UseNone
}

\begin{document}
\maketitle
\thispagestyle{empty}

%\cleardoublepage
%\pagenumbering{roman}
%\setcounter{page}{1}
%\tableofcontents
%  \newpage
%\listoffigures
%  \listoftables

\pagenumbering{arabic}
\setcounter{page}{1}

\section{Introducción}
Se requiere hallar un valor aproximado para $\sqrt{2}$ por medio de dos métodos distintos; por aproximación por serie de Taylor y por Newton-Raphson.
Usaremos diferentes grillas numéricas de punto flotante de 2, 4, 6 y 8 dígitos con redondeo simétrico.
A continuación justificaremos cada método.

\subsection{Polinomio de Taylor}

La expresión general del polinomio de Taylor es la siguiente:

\begin{align}
		f_{(x)}&=\sum_{k=0}^{\infty}\dfrac{f^{(k)}_{(x_{0})}\cdot{(x-x_{0})}^k}{k!}
\end{align}

Por lo tanto, aplicándolo a la función: $f_{(x)}=\sqrt{1+x}$ alrededor de $0$, desarrollamos la serie del polinomio.

\begin{align}
	f_{(x)}&=(1+x)^{\frac{1}{2}}\\	
	f^{\prime}_{(x)}&=\frac{1}{2}\cdot(1+x)^{\frac{-1}{2}}\\	
	f^{\prime\prime}_{(x)}&=\frac{-1}{4}\cdot(1+x)^{\frac{-3}{2}}\\
	f^{\prime\prime\prime}_{(x)}&=\frac{3}{8}\cdot(1+x)^{\frac{-5}{2}}\\
	f^{(4)}_{(x)}&=\frac{-15}{16}\cdot(1+x)^{\frac{-7}{2}}
\end{align}

De estas derivadas podemos deducir la formula general de las derivadas de orden $n \geq 2$.

\begin{align}
	f^{(n)}_{(x)}&=\frac{{-1}^{n-1}}{2^n}\cdot(1+x)^{\frac{-(2n-1)}{2}}\cdot\prod^{n-2}_{j=0} {(2\cdot j+1)} & \forall n \geq 2
\end{align}

Demostraremos que esta expresión es correcta para las derivadas sucesivas,
tomando la (n+1)-ésima derivada de f, mediante la fórmula general, y comparándola con la derivada de $f^{(n)}_{x}$.

Queremos:

\begin{align}
	{f^{(n)}_{(x)}}^\prime&=f^{(n+1)}_{(x)}
\end{align}

Veremos si se cumple el paso inductivo:

\begin{align}
	{f^{(n)}_{(x)}}^\prime&=\frac{{-1}^{n-1}\cdot -1}{2^n \cdot 2}\cdot(1+x)^{\frac{-(2n+1)}{2}}\cdot \left( \prod^{n-2}_{j=0} {(2\cdot j+1)} \right) \cdot(2n-1)\\
	{f^{(n)}_{(x)}}^\prime&=\frac{{-1}^{n}}{2^n \cdot 2}\cdot(1+x)^{\frac{-(2n+1)}{2}}\cdot \left( \prod^{n-2}_{j=0} {(2\cdot j+1)} \right) \cdot(2n-1)\\
	f^{(n+1)}_{(x)}&=\frac{{-1}^{n+1-1}}{2^{n+1}}\cdot(1+x)^{\frac{-(2\cdot(n+1)-1)}{2}}\cdot\prod^{n+1-2}_{j=0} {(2\cdot j+1)}\\
	f^{(n+1)}_{(x)}&=\frac{{-1}^{n}}{2^{n+1}}\cdot(1+x)^{\frac{-(2n+1)}{2}}\cdot \left( \prod^{n-2}_{j=0} {(2\cdot j+1)} \right) \cdot (2\cdot(n-2+1)+1) \\
	f^{(n+1)}_{(x)}&=\frac{{-1}^{n}}{2^{n+1}}\cdot(1+x)^{\frac{-(2n+1)}{2}}\cdot \left( \prod^{n-2}_{j=0} {(2\cdot j+1)} \right)\cdot (2n-1)\\
	f^{(n+1)}_{(x)}&={f^{(n)}_{(x)}}^\prime
\end{align}

A continuación verificaremos entonces que esta expresión es realmente compatible con las derivadas de un orden mayor a $n \geq 2$ por inducción.

\begin{align}	
	f^{(2)}_{(x)}&=\frac{{-1}^{2-1}}{2^2}\cdot(1+x)^{\frac{-(2\cdot2-1)}	
		{2}}\cdot\prod^{2-2}_{j=0} {(2\cdot j+1)} \\	
	f^{(2)}_{(x)}&=\frac{-1}{4}\cdot(1+x)^{\frac{-3}{2}}\\
	f^{(3)}_{(x)}&=\frac{{-1}^{3-1}}
		{2^3}\cdot(1+x)^{\frac{-(2\cdot3-1)}
		{2}}\cdot\prod^{3-2}_{j=0} {(2\cdot j+1)} \\
	f^{(3)}_{(x)}&=\frac{3}{8}\cdot(1+x)^{\frac{-5}{2}}
\end{align}

Demostramos entonces que la sucesión de las derivadas planteadas, es válida para $n=2$, $n=3$ y para $n+1$, por lo cual es válida también para toda $n > 3$.

Ahora si realizamos el desarrollo de McLaurin, o de Taylor centrado en $x_0=0$, obtendremos:

\begin{align}
	f_{(x)}&= 	
		f_{(x_0)} +
		f^{\prime}_{(x_0)} \cdot (x-x_0) +
		\frac {f^{\prime\prime}_{(x_0)} \cdot (x-x_0)^2}{2!} +
		\sum_{k=3}^{\infty}\dfrac{f^{(k)}_{(x_{0})}\cdot{(x-x_{0})}^k}{k!}
\end{align}

Reemplazamos la $f_{(x)}$ y sus derivadas, en el polinomio, alrededor de $x_0$:

\begin{align}				
	f_{(x)}&= 	
		(1+x_0)^{\frac{1}{2}} +
		\frac{1}{2 \cdot 1!}\cdot(1+x_0)^{\frac{-1}{2}} \cdot (x-x_0) + 
		\frac{-1}{4 \cdot 2!}\cdot(1+x_0)^{\frac{-3}{2}} \cdot (x-x_0)^2+	
		\sum_{k=3}^{\infty}\dfrac{f^{(k)}_{(x_{0})}\cdot{(x-x_{0})}^k}{k!}\\	
	f_{(x)}&= 	
		(1+x_0)^{\frac{1}{2}} +
		\frac{1}{2}\cdot(1+x_0)^{\frac{-1}{2}} \cdot (x-x_0) + 
		\frac{-1}{8}\cdot(1+x_0)^{\frac{-3}{2}} \cdot (x-x_0)^2+	
		\sum_{k=3}^{\infty}\dfrac{f^{(k)}_{(x_{0})}\cdot{(x-x_{0})}^k}{k!}
\end{align}
\begin{align}
		f^{(n)}_{(x_0)}&=\frac{{-1}^{n-1}}{2^n}\cdot(1+x_0)^{\frac{-(2n-1)}{2}}\cdot\prod^{n-2}_{j=0} {(2\cdot j+1)} & \forall n \geq 2
\end{align}

Reemplazando $x_0=0$ llegamos a la expresión:

\begin{align}
	f_{(x)}&\cong 	
		1 +
		\frac{1}{2} \cdot x + 
		\frac{-1}{8} \cdot x^2+	
		\sum_{k=3}^{\infty}\dfrac{f^{(k)}_{(0)}}{k!}\cdot{x}^k	\\
	f^{(n)}_{(0)}&=
		\frac{{-1}^{n-1}}{2^n}\cdot\prod^{n-2}_{j=0} {(2\cdot j+1)} & \forall n \geq 2 \\
	f_{(x)}&\cong 	
		1 +
		\frac{1}{2} \cdot x + 
		\frac{-1}{8} \cdot x^2+	
		\sum_{k=3}^{\infty}\frac{{-1}^{k-1}}{2^k} \cdot \dfrac{\prod^{k-2}_{j=0} {(2\cdot j+1)}}{k!}\cdot{x}^k	
\end{align}


Especializando el polinomio en $x=1$:
\begin{align}
\sqrt{1+x}&= 	
		1 +
		\frac{1}{2} + 
		\frac{-1}{8}+	
		\sum_{k=3}^{\infty}\frac{{-1}^{k-1}}{2^k} \cdot \dfrac{\prod^{k-2}_{j=0} {(2\cdot j+1)}}{k!}
\end{align}

Queda demostrado de esta manera, que el siguiente polinomio sirve para aproximar $\sqrt{2}$
\begin{align}
P_{(x)}&= 	
		1 +
		\frac{1}{2} + 
		\frac{-1}{8}+	
		\sum_{k=3}^{n}\frac{{-1}^{k-1}}{2^k} \cdot \dfrac{\prod^{k-2}_{j=0} {(2\cdot j+1)}}{k!}
\end{align}
 
\subsection{Sucesión por Newton-Raphson}

El segundo metodo para aproximar el valor de $\sqrt{2}$ es un método de punto fijo para el cual necesitaremos la raíz de una $f_{(x)}$ a hallar:

\begin{align}
	x&=\sqrt{2}\\
	x^2&=2\\
	x^2-2&=0
\end{align}

Entonces construimos dicha función para buscar su raíz.

\begin{align}
	f_{(x)}&=x^2-2
\end{align}

Recordando la forma de Newton-Raphson:

\begin{align}
	x_{n+1}&=x_n-\dfrac{f_{(x_n)}}{f^\prime_{(x_n)}}
\end{align}

A continuación reemplazamos la función y su derivada en la sucesión:

\begin{align}
	x_{n+1}&=x_n-\dfrac{x^2_n-2}{2x_n}\\
	x_{n+1}&=\dfrac{x_n}{2}-\dfrac{1}{x_n}
\end{align}

Notamos, habiendo desarrollado la sucesión mediante Newton-Raphson, que esta expresión sirve para aproximar el valor de $\sqrt{2}$.

\section{Desarrollo}
	\lstinputlisting[caption=TP1T.m]{../octave/TP1T.m}
	\lstinputlisting[caption=TP1NR.m]{../octave/TP1NR.m}
	\lstinputlisting[caption=puntoFijo.m]{../octave/puntoFijo.m}
	\lstinputlisting[language=make, caption=makefile]{../makefile}

\section{Resultados}

\subsection{Método: Serie de Taylor}
	\input{taylor.part.tex}

\subsection{Método: Newton-Raphson}
	\input{nr.part.tex}

\section{Conclusiones}
En la tabla de resultados observamos la aproximación obtenida y el error relativo por cada método según la grilla utilizada en cada caso.

Evaluando el error en cada caso, notamos inmediatamente que el error por truncamiento se reduce más cuanto mayor sea la cantidad de iteraciones más allá del método o la grilla utilizada, lo cual se condice con las condiciones tanto del polinomio como de la sucesión, que indican que a mayor cantidad de iteraciones más se acercará el resultado al valor buscado, $\sqrt{2}$.

Por otro lado, los errores por redondeo también se reducen a medida que aumenta la cantidad de iteraciones, ya que cuanto mayor es la cantidad de operaciones, mayor es la importancia de la grilla elegida.
Esto es fácil de comprobar comparando la diferencia de errores entre las grillas cuando se hacen pocas iteraciones con uno de los métodos, con la diferencia de errores entre las grillas cuando se hacen más iteraciones.
Por ejemplo, todas las grillas tienen el mismo error cuando lo calculamos con una iteración usando el método Newton-Raphson, pero realizando 4 iteraciones se puede observar que cuanto mayor sea la mantisa de la grilla menor será el error obtenido.

Por último, analizando los resultados obtenidos, observamos que aproximando mediante la sucesión de Newton-Raphson alcanzamos un valor con menor error que mediante el polinomio de Taylor.
Teniendo en cuenta también la cantidad de operaciones que precisa cada algoritmo, la velocidad con que se ejecuta el algoritmo utilizando el método de Newton-Raphson es mayor que la velocidad mediante el polinomio de Taylor ya que involucra una mayor cantidad de operaciones.
Por lo tanto, para aproximar el valor de $\sqrt{2}$ con mayor precisión y velocidad resulta conveniente utilizar el método de Newton-Raphson con una grilla de 8 dígitos en la mantisa.

\appendix
\section{Apéndice: Resultados adicionales}

Para perfeccionar el informe, se realizó un análisis posterior.
Con la experiencia ganada en el segundo informe, se reescribieron las
implementaciones de los métodos, logrando separar el resolvedor por
Newton-Raphson en un resolvedor general de punto fijo y una invocación desde el
reporte principal que lo llama con la función a evaluar.

Como mejoras posteriores, podría separarse también el resolvedor por serie de
Taylor en un método aparte también reaprovechable.
Aunque el resolvedor por Newton-Raphson ya es reaprovechable independientemente,
la verificación de argumentos también sería útil si se quiere reaprovechar el
código de forma más segura.

Se generaron gráficos de la evolución de los errores de aproximación para cada
método con grillas de distinto tamaño.
En ambos se puede apreciar cómo mejora la precisión a mayor cantidad de dígitos
en la mantisa.

En el caso de la aproximación por serie de Taylor, puede verse cómo las
distintas variaciones se comportan de forma similar hasta que el error se acerca
a la precisión buscada.
Para 2 dígitos, los términos siguientes directamente son menores a la precisión,
con lo que al sumarlos al resultado parcial de la sumatoria, éste no varía.
Para 4 dígitos, se conservan pocos primeros dígitos de cada término; si se
hicieran más iteraciones, se llegaría al punto que ningún dígito de los términos
nuevos se conserven.
Puede verse que para 6 y 8 dígitos significativos no se da el caso aún; serían
necesarias más iteraciones.

\begin{figure}[!ht]
	\caption{Errores de aproximación por Taylor}
	\begin{center}
		\includegraphics[scale=0.5]{erroresT}
	\end{center}
\end{figure}

En el caso de aproximación por punto fijo con la expresión de Newton-Raphson,
por otro lado, puede verse que, a mayor cantidad de dígitos, el error es siempre
menor.
Puede verse de nuevo cómo los errores se estabilizan por debajo de la precisión,
ésto se debe a que el resultado de la evaluación del candidato termina
redondeándose al mismo.
\begin{figure}[!ht]
	\caption{Errores de aproximación por Newton-Raphson}
	\begin{center}
		\includegraphics[scale=0.5]{erroresNR}
	\end{center}
\end{figure}

\end{document}
